#ifndef TIM_VECTOR_H
#define TIM_VECTOR_H
#include <bits/stdc++.h>

namespace tim
{
	#define default_capacity 3

	template<typename T>
	class vector//defintion of my vector
	{
		protected:
			int _size;//当前有效元素量
			int capacity;//容量
			T* elem;//元素空间
			bool sorted = false;//是否排序标志
			bool expand();//扩容，倍增式，均摊复杂度o（1）复杂度o（n）
			bool shrink();//缩容，同倍减式
			bool bubble_sort(bool order);//冒泡排序
			bool merge_sort(bool order, int lo, int hi);//归并排序

		public:
			vector();//按默认空间生成
			vector(int c, T const& value = T()); //开空间构造, 可选默认空值
			vector(T* begin, T* end);//从T数组中生成
			vector(std::vector<T>& std_vector);//从标准向量生成
			vector(tim::vector<T>& old_one);//从同样的向量生成
			vector(tim::vector<T>& old_one, int begin, int end);//从同样的向量生成，可选开始与结束
			bool is_empty();//判空
			int size() { return _size; };//判断尺寸
			T& operator[] (int n);//仿数组接口
			bool sort(bool mode, bool order);//排序, 小数据时选择o（n2）的冒泡排序，大数据时选择o（n）的归并排序， 因为递归压栈耗时, order表正逆序
			bool insert(int n, T const& e);//插入，复杂度o（n）
			bool remove(int begin, int end);//区间删除，复杂度o（n），规定左闭右开
			T remove(int n);//删除特例，复杂度o（n）
			bool change(int n, T const& e);//改变元素值，复杂度o（n）
			bool uniquify(bool is_sort);//唯一化，选择是否排序
			bool is_exist(T const& e);//判断存在, 时间复杂度o（n）
			int find(int n);//二分查找, 会根据是否排序标志进行调用排序
			int find(T const& e);//按元素查找
			bool append(T const& e);//加入新元素
			template<typename VST>
			void traverse(VST& visit);//遍历，时间复杂度o（n）
			~vector();
	};
}

template<typename T>
tim::vector<T>::vector()
{
	_size = 0;
	capacity = default_capacity;
	elem = new T[capacity];
}

template<typename T>
tim::vector<T>::~vector()
{
	delete []elem;
}

template<typename T>
bool tim::vector<T>::is_empty()
{
	return _size == 0;
}

template<typename T>
tim::vector<T>::vector(int c, T const& value): _size(c), capacity(c), elem(new T[c])
{
	for (int i = 0; i < capacity; i++)
		elem[i] = value;
}

template<typename T>
tim::vector<T>::vector(tim::vector<T>& old_one): _size(old_one.size()), capacity(old_one.size()), elem(new T[old_one.size()])
{
	for (int i = 0; i < _size; i++)
		elem[i] = old_one[i];
}

template<typename T>
tim::vector<T>::vector(tim::vector<T>& old_one, int begin, int end): _size(end - begin), capacity(end - begin), elem(new T[end - begin])
{
	for (int i = 0; i < _size; i++)
		elem[i] = old_one[begin + i];
}

template<typename T>
T& tim::vector<T>::operator[](int n)
{
	return elem[n];
}

template<typename T>
tim::vector<T>::vector(std::vector<T>& std_vector)
{
	_size = std_vector.size();
	capacity = _size;
	elem = new T[capacity];

	for (int i = 0; i < _size; i++)
		elem[i] = std_vector[i];
}

template<typename T>
tim::vector<T>::vector(T* begin, T* end)
{
	_size = end - begin;
	capacity = _size;
	elem = new T[capacity];

	for (int i = 0; i < _size; i++)
		elem[i] = begin[i];
}

template<typename T>
bool tim::vector<T>::expand()
{
	if (_size < capacity) return false;

	capacity *= 2;
	T* old_elem = elem;
	elem = new T[capacity];

	for (int i = 0; i < _size; i++)
		elem[i] = old_elem[i];
	delete old_elem;
	return true;
}

template<typename T>
bool tim::vector<T>::shrink()
{
	if (_size + 1 > capacity / 2) return false;

	capacity /= 2;
	T* old_elem = elem;
	elem = new T[capacity];

	for (int i = 0; i < _size; i++)
		elem[i] = old_elem[i];
	delete old_elem;
	return true;
}

template<typename T>
bool tim::vector<T>::insert(int n, T const& e)
{
	if (n > capacity) return false;

	expand();
	for(int i = _size; i > n; i--)
		elem[i] = elem[i - 1];
	elem[n] = e;
	_size += 1;
	return true;
}

template<typename T>
bool tim::vector<T>::remove(int begin, int end)
{
	if (begin > end or begin > capacity or end > capacity)
		return false;

	int n = end - begin;
	for (int i = begin; i < _size - n; i++)
		elem[i] = elem[i + n];
	_size -= n;
	shrink();
	return true;
}

template<typename T>
bool tim::vector<T>::change(int n, T const& e)
{
	if (n > _size) return false;
	elem[n] = e;
	return true;
}

template<typename T>
T tim::vector<T>::remove(int n)
{
	T re = elem[n];
	remove(n, n + 1);
	return re;
}

template<typename T>
template<typename VST>
void tim::vector<T>::traverse(VST& visit)
{
	for(int i = 0; i < _size; i++)
		visit(elem[i]);
}

template<typename T>
bool tim::vector<T>::is_exist(T const& e)
{
	for (int i = 0; i < _size; i++)
		if (e == elem[i]) return true;
	return false;
}

template<typename T>
bool tim::vector<T>::sort(bool mode, bool order)
{
	sorted = true;
	return mode ? bubble_sort(order): merge_sort(order, 0, _size);
}

template<typename T>
bool tim::vector<T>::bubble_sort(bool order)
{

	for (int i = _size; i > 0; i--)
		for (int j = 0; j < i - 1; j++)
			if ((elem[j] > elem[j + 1]) == order) {
				T temp;

				temp = elem[j];
				elem[j] = elem[j + 1];
				elem[j + 1] = temp;
			}

	return true;
}

template<typename T>
bool tim::vector<T>::merge_sort(bool order, int lo, int hi)
{
	if (hi - lo < 2) return true;
	int mi = (hi + lo) >> 1;
	merge_sort(order, lo, mi);
	merge_sort(order, mi, hi);

	T* left = new T[mi - lo];//前子向量
	T* right = new T[hi - mi];//后子向量

	for (int i = 0; i < mi - lo; i++) left[i] = elem[lo + i];
	for (int i = 0; i < hi - mi; i++) right[i] = elem[mi + i];

	for (int i = 0, l = 0, r = 0; i < hi - lo; i++)
		if (l == mi - lo) elem[lo + i] = right[r++];
		else if (r == hi - mi) elem[lo + i] = left[l++];
		else
			if ((left[l] > right[r]) == order) elem[lo + i] = right[r++];
			else elem[lo + i] = left[l++]; //分三种情况比较两有序向量

	delete []left;
	delete []right;
	return true;
}

template<typename T>
int tim::vector<T>::find(T const& e)
{
	int cnt = 0;
	for (; cnt < _size; cnt++) if (e == elem[cnt]) return cnt;
	return -1;
};

template<typename T>
bool tim::vector<T>::uniquify(bool is_sort)
{
	int current = 0;
	int temp = 0;
	if (_size <= 1) return false;//双指针

	if (is_sort) {
		while(++temp < _size)
			if (elem[current] != elem[temp])
				elem[++current] = elem[temp];
		_size = current + 1;//WTF?
		shrink();
	}//如果排序了
	else {
		int i = 0;
		while (i < _size - 1)
			(elem[i] == elem[i + 1]) ? remove(i + 1): i++;
	}

	return true;
}

template<typename T>
bool tim::vector<T>::append(const T &e)
{
	expand();
	elem[_size] = e;
	_size++;
	return true;
}

#endif
